For link aggregation trunks to work effectively, load distribution among the links must be as balanced as possible. Multi-link trunking provides access pipes to servers where data is concentrated. As the deployment of sophisticated applications such as intranets, groupware, Web-based applications, and document imaging place new demands on network performance, multi-link load balancing delivers faster response times to user data requests by minimizing bottlenecks at a server. While other system components also impact performance, server interfaces with multi-link load balancing provide dramatic improvements in throughput at a relatively low cost.
In addition to flexibility, multiple links provide higher availability and resiliency as well as improved fault tolerance. The resiliency provided by load balancing provides high-availability network paths, which are increasingly important as more and more mission-critical and other applications are deployed in networks.
Although multi-link trunking has many benefits, a major challenge is how to distribute and balance traffic across various links. An effective load balancing scheme will result in a full utilization of invested resource and maximize available performance. Current load balancing solutions have a number of limitations. They often fail to provide fair bandwidth allocation, or introduce significant reordering of packets. Transport protocols, such as Transmission Control Protocol (TCP), require reasonable limits on packet reordering and loss in order to function optimally. For example, a fast retransmit algorithm makes assumptions about a level of packet reordering, and induces spurious retransmissions in the face of excessive reordering. It is therefore important to ensure that any multi-link load balancing scheme limits packet reordering and loss as much as possible.
Various algorithms have been proposed for scheduling traffic in multi-link trunks, such as random packet load balancing, round-robin packet load balancing, random flow load balancing, round-robin flow load balancing, and address-based load balancing, for example.
With random packet load balancing, as packets arrive at a multi-link trunk, the packets are randomly distributed, packet-by-packet over each link. This provides a simple load balancing implementation but has a number of drawbacks. For example, random fluctuations in traffic can result in each link being loaded differently. As a result, the performance of the system is hard to predict. Also, packets within a flow or session may arrive at their destination out of order (e.g., mis-sequenced). Out of order delivery may result in TCP clients retransmitting packets thereby adding to network load. When a TCP receiver receives a segment with an out-of-order sequence number value, the receiver is required to generate an immediate acknowledgment (ACK) of the highest in-order data byte received (e.g., a duplicate ACK of an earlier transmission). The purpose of the duplicate ACK is to inform the sender that a segment was received out of order, as well as the sequence number expected. When the TCP sender receives three duplicate ACKs, it immediately retransmits the lost segment.
A round-robin packet load balancing approach distributes each arriving packet on a different link in a round-robin fashion. This means that each link is used on a rotating basis for each arriving packet. This scheme is simple to implement with little processor overhead. However, the round-robin packet load balancing approach fails to provide adequate bandwidth allocation in the presence of variable packet sizes. Also, since packets for a given session go out on different links, the packets may reach their destination out of order. For TCP, this can force clients to retransmit packets thereby resulting in increased traffic and a loss of performance. Weighted round robin load balancing is similar to round robin, but each link in the trunk is assigned a static weight based on some view of the capacity of the link. Packets are forwarded to the links in proportion to their weighting. More sophisticated round-robin packet schemes that can handle variable packet sizes and provide fair load sharing over links having different capacities are available.
With a random flow load balancing approach, each new flow or session (e.g., TCP connection) is randomly assigned to a link. Thus, all packets in the flow follow the same path. The scheme is simple to implement and does not result in misordering of packets within a flow. However, random fluctuations in traffic can cause each link to be loaded differently. As a result, it is hard to predict system performance in this case.
A round-robin flow load balancing approach distributes each new flow on a different link in a round-robin fashion. Although this method preserves packet sequencing, random fluctuations in traffic in the connections can cause each link to be loaded differently. It is also difficult to predict system performance in this case.
Typically, address-based load balancing schemes select a link on which a packet is to be transmitted based on the result of a hashing mechanism that uses one or more identifiers in the packet. Typically, simple algorithms may include hashing of a destination medium access control (MAC) address, or hashing of a flow identifier, etc. to designate a link to each flow.
Another conventional method involves using an exclusive-OR (X-OR) operation to determine what link in the trunk will be taken by an arriving packet. For a four-link trunk, a X-OR operation can be performed on the last two lowest-order bits of the source and destination MAC addresses. This operation yields one of four results: ((0 0), (0 1), (1 0), or (1 1). Each of these values points to a link in the bundle. In the case of a two-link trunk, only a single bit is used in the X-OR operation. This scenario yields two possible results, each pointing to a link in the bundle. The X-OR operations result in the sequencing of packets and, if the destination also performs the same operation, the same link is taken because the X-OR operation results in the same value in both directions. There are circumstances where one address in a source-destination pair is a constant. For example, a destination might be a server or, even more likely, a router. However, as long as one address (source or destination) is different, there is still a chance of statistical load balancing. If the two addresses are constant as would be the case and/or if the traffic is between two routers (or two servers), then no load balancing exists. Although this method preserves packet sequencing, random fluctuations in traffic in the connections can cause each link to be loaded differently. It is also hard to predict the system performance in this case.
Other methods use only a destination MAC address where the link selected is based on low-order bits of the MAC address. A disadvantage of this method is that server traffic may not be evenly balanced across all links, since this method depends on destination address distribution of the clients. Another drawback, particularly in an Ethernet MAC address-based scheme, is that all clients lying across a router will be assigned to the same link, since they all contain the same destination MAC address—which is the router's MAC address. In this case, the traffic will not be load balanced thereby creating major problems for a typical IP network, in which at least one router can be found between most clients and servers.
Multi-link trunking provides various benefits. For example, multi-link trunking protects investments in existing infrastructure. It further provides a cost effective solution for applications which need incremental scaling. For example, multi-link trunking supports incremental scaling rather than exponential scaling of server and switch ports. Also, it allows for quick performance upgrades before procurement of new hardware, where point-to-point carrying capacity of a link may be scaled according to a desired bandwidth.
Currently, it may be more cost effective to trunk multiple lower speed links. This is because traditional end-systems do not fully utilize a high bandwidth link (e.g., a 1 Gbps link), available copper links and supported distances are more pervasive for lower speed links, and lower speed network interface cards (NICs) and switch ports are more affordable.
Multi-link load balancing technology is of growing importance as network managers and designers seek to upgrade the performance and availability of existing infrastructures as inexpensively and efficiently as possible. Multi-link load balancing on several lower capacity links (e.g., 10, 100 Mbps) provides a cost-effective way to expand (e.g., server-to-switch, switch-to-switch) link bandwidth to relieve congestion before making a transition to higher capacity single links (e.g., 1, 10 Gbps).
In view of the foregoing, it would be desirable to provide a technique for adaptively load balancing connections in multi-link trunks which overcomes the above-described inadequacies and shortcomings. More particularly, it would be desirable to provide a technique for adaptively load balancing connections in multi-link trunks in an efficient and cost effective manner.